00100	                         STANFORD UNIVERSITY		       
00200	                    COMPUTER  SCIENCE  DEPARTMENT
00300	                            SPRING,   1974
00400	
00500	                   MODELS  OF  THOUGHT  PROCESSES
00600	                     (artificial intelligence)
00700				     CS  224
00800		              T Th 1:15-2:30, Room 300
00900	
01000	            Handout #4       April 25, 1974
01100	
01200	1. Administrative details:  New TA office hours are T 11-1:15,
01300		Th 12-1:15, 2:30-3:15. Office is Polya 263, ext. 1646.
01400	
01500	2. Homework set 4.  Due: May 2, 1974.
01600		Your assignment, Mr. Phelps, is to propose an information
01700	processing model of psychology, test its predictions against a
01800	human protocol, and discuss the results. And none of this 'if you
01900	choose to accept it'  nonsense.  Hint: the following constraints
02000	will reduce this effort from ~5 years down to about five hours.
02100		(a) Concentrate only on how a human solves the missionaries
02200	and cannibals problem. Don't worry about other tasks or skills (such 
02300	as learning, cognition, generalization, forgetting, motor 
02400	coordination, emotions, drives) which are obviously not as important.
02500		(b) If you don't want to invent a new model of how a person
02600	solves the M&C problem, you may select one you have heard about and
02700	try to apply it to M&C.  We suggest that you gather data before devis-
02800	ing a new model, but of course you may create it from scratch.  The
02900	GPS formalism seems suitable, although others may be better.
03000		(c) Once you have a model, actually describe how your model
03100	finds a solution to the M&C problem.
03200		(d) Take a protocol from a human subject who produces a
03300	running commentary on his/her own process of solving the problem.
03400	Quit when the subject solves the problem or gives up, or when you
03500	give up. Don't give up until you've at least finished reading the
03600	assignment, however. Be sure to record the protocol (paper,
03700	magnetic tage, etc.)
03800		(e) Reduce the mass of raw protocol data to a representation
03900	in which it may be tested against your proposed theory. If you are
04000	looking for a good place to kluge (cheat), this is it.  A problem
04100	behavior graph is a representation of the type we're talking about.
04200		(f) Validate or invalidate your model by comparing the
04300	subject's performance with the model's predictions. Devise some
04400	measure of agreement (no. of states in common;  number of false
04500	paths tried; relative times between moves; point at which the
04600	subject/model gave up; etc.) Suggest explanations for any disagreement
04700	with your model (perhaps propose a new model).  If there was no 
04800	difference, explain this very very carefully, and consider a career
04900	in information processing psychology.
05000		(g) Discuss the difficulties you encountered at each stage
05100	of your research.  Was this a good research paradigm?  Do people
05200	really generate problem behavior graphs in their head?
05300		(h) You may work in small groups. Don't spend too much time
05400	on any one phase: try each part to get the feel of it, at least.
05500	It is unimportant whether your model is validated or invalidated in
05600	step (f).
05700		(i) If this assignment kills you, the secretary will disavow
05800	any knowledge of your actions.  So will the professor.  Good luck, Jim.
     

00100	3. Comments on homework assignment #2.
00200		Many people seem to have missed the concept of doing an ordered
00300	search:  for each node, compute the f∧ value as the sum of the g value
00400	(cost to that node) plus the h∧ value of that node. Expand that tip node
00500	having the lowest f∧ value -- regardless where in the tree it is.
00600	Compute f∧ values of new nodes, and again look all through the tree
00700	for the node with the lowest f∧ value to expand next.
00800		As examples, we shall mention a few h∧ functions, and show the
00900	corresponding trees for three of them.
01000		h∧ ≡ 0.  Clearly 0 ≤ h∧ ≤ h. Graphed in Fig. 1.
01100		h∧ ≡ (cost of the cheapest arc anywhere)x(number of cities left
01200			to visit, including A). Graphed in Fig. 2.
01300		h∧ ≡ sum, over cities still to be visited, of the cheapest arc
01400			into that city.
01500		h∧ ≡ sum, over unvisited cities, of the cheapest arc between that
01600			city and any other unvisited city. Graphed in Fig. 3.
01700		h∧ ≡ dist. from A to nearest unvisited city, plus distance from
01800			current node to nearest unvisited city, plus the sum,
01900			over unvisited cities excluding A, of the two shortest
02000			distances connecting that city to other unvisited cities.
02100		h∧ ≡ h.  Note that this requires a great deal more work to compute
02200			than h∧ identically zero.
02300	
02400	Many more h∧ functions were proposed, but some of them violated the
02500	admissability of A*.  For example, many were not lower bounds on h.
02600	A key concept is that as the complexity of calculating h∧ increases
02700	more and more, there comes a point where it's no better to spend the
02800	time computing f∧ = g + h∧ for each node than it would be to simply
02900	generate every possible node.  The last h∧ exemplifies this.  Note
03000	that the h∧ graphed in figure 3 is relatively simple, yet directs the
03100	search almost always along a goal path.
03200	
03300	
03400	
03500	
03600	(The graphs were done by T. Pettit, in full color, and lost something
03700	in the photocopying process)